package leetcode.editor.cn;
//给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。 
//
// 
//
// 示例 1： 
//
// 
//输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
//输出： True
//说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。 
//
// 示例 2: 
//
// 
//输入: nums = [1,2,3,4], k = 3
//输出: false 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= len(nums) <= 16 
// 0 < nums[i] < 10000 
// 每个元素的频率在 [1,4] 范围内 
// 
//
// Related Topics 位运算 记忆化搜索 数组 动态规划 回溯 状态压缩 👍 928 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution124 {

    public boolean canPartitionKSubsets1(int[] nums, int k) {
        // 大小不对，排除
        if (k > nums.length) {
            return false;
        }
        int sum = 0;
        for (int v : nums) sum += v;
        // 不能均分，排除
        if (sum % k != 0) return false;

        // 理论上每个桶（集合）中数字的和
        int target = sum / k;
        boolean[] used = new boolean[nums.length];
        // 穷举，看看 nums 是否能划分成 k 个和为 target 的子集
        return backtrack1(k, 0, nums, 0, used, target);
    }

    private boolean backtrack1(int k, int sum, int[] nums, int start, boolean[] used, int target) {

        if (k == 0) {
            return true;
        }

        if (sum == target) {
            return backtrack1(k - 1, 0, nums, 0, used, target);
        }

        for (int i = start; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            if (sum + nums[i] > target) {
                continue;
            }

            used[i] = true;
            sum += nums[i];

            if (backtrack1(k, sum, nums, i + 1, used, target)) {
                return true;
            }

            used[i] = false;
            sum -= nums[i];

        }
        return false;
    }


    public boolean canPartitionKSubsets(int[] nums, int k) {
        // 大小不对，排除
        if (k > nums.length) {
            return false;
        }
        int sum = 0;
        for (int v : nums) sum += v;
        // 不能均分，排除
        if (sum % k != 0) return false;

        // k 个桶（集合），记录每个桶装的数字之和
        int[] bucket = new int[k];
        // 理论上每个桶（集合）中数字的和
        int target = sum / k;

        // 如果我们提前对 nums 数组排序，把大的数字排在前面，
        // 那么大的数字会先被分配到 bucket 中，对于之后的数字，
        // bucket[i] + nums[index] 会更大，更容易触发剪枝的 if 条件
        /* 降序排序 nums 数组 */
        Arrays.sort(nums);
        for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
            // 交换 nums[i] 和 nums[j]
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        /*******************/

        // 穷举，看看 nums 是否能划分成 k 个和为 target 的子集
        return backtrack(nums, 0, bucket, target);
    }

    private boolean backtrack(int[] nums, int index, int[] bucket, int target) {
        if (index == nums.length) {
            for (int buc : bucket) {
                if (buc != target) {
                    return false;
                }
            }
            return true;
        }
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] + nums[index] > target) {
                continue;
            }
            // 将 nums[index] 装入 bucket[i]
            bucket[i] += nums[index];
            // 递归穷举下一个数字的选择
            if (backtrack(nums, index + 1, bucket, target)) {
                return true;
            }
            // 撤销选择
            bucket[i] -= nums[index];
            // 这里可能index还没到nums.length，但是出现了无法凑成target的数，所以直接返回break，然后fasle就行
            if (bucket[i] == 0) {
                // nums[index]找不到可以凑成target的数
                break;
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
